 function zhangxinyu2302
 fprintf('\n信息与计算科学集中实践环节')
 fprintf('\n        数学实验')
 fprintf('\n   信息2302班--张鑫宇')
 fprintf('\n       最短路径程序')
 e=[1 2 2;1 3 8;1 4 1;2 3 6;2 5 1;3 4 7;3 5 5;3 6 1;3 7 2;4 7 9;5 6 3;5 8 9;6 7 4;6 8 6;7 8 5];
sroute(e,0)
 end
function route = sroute(G,opt)
while 1
    if G(1,1)==0
        A=G;
        n=size(A,1);
        A1=A;
        A1(A1==inf)=0;
        M=sum(sum(A1));
        A1(A1==0)=M;
        A=A1-M*eye(n);
        break;
    else
        e=G;
        n=max([e(:,1);e(:,2)]);
        m=size(e,1);
        M=sum(e(:,3));
        A=M*ones(n,n);
        for k=1:m
            A(e(k,1),e(k,2))==e(k,3);
            if opt==0
                A(e(k,2),e(k,1))=e(k,3);
            end
        end
        A=A-M*eye(n);
    end
    break
end
pb(1:length(A))=0;
pb(1)=1;
index1=1;
index2=ones(1,length(A));
d(1,length(A))=M;
d(1)=0;
temp=1;
while sum(pb)<length(A)
    tb=find(pb==0);
    d(tb)=min(d(tb),d(temp)+A(temp,tb));
    tmpb=find(d(tb)==min(d(tb)));
    temp=tb(tmpb(1));
    pb(temp)=1;
    index1=[index1,temp];
    index=index1(find(d(index1)==d(temp)-A(temp,index1)));
    if length(index)>=2
        index=index(1);
    end
    index2(temp)=index;
end 
route=[1:n;d;index2];
end


